﻿#include "as_tree.h"

AvlTree::AvlTree()
	: root_(nullptr)
{

}

AvlTree::~AvlTree()
{
	remove(root_);
}

AvlNode *AvlTree::CreateNode(const int &k)
{
	AvlNode *n = new AvlNode(k);
	return n;
}

int AvlTree::height(const AvlNode *root)
{
	return 0;
}

bool AvlTree::insert(const int &k)
{
	AvlNode *n = this->CreateNode(k);
	if (root_ == nullptr)
	{
		root_ = n;
		return true;
	}

	AvlNode *p, *sp;
	sp = p = root_;
	while (p != nullptr)
	{
		sp = p;
		if (k < p->key)
		{
			p = p->l;
		}
		else if (k > p->key)
		{
			p = p->r;
		}
		else
		{
			delete n;
			n = nullptr;
			return false;
		}
	}
	if (k < sp->key)
		sp->l = n;
	else
		sp->r = n;
	n->p = sp;
	return true;
}

bool AvlTree::remove(const int &k)
{
	AvlNode *t = find(root_, k);
	if (t != nullptr)
		remove(t);
	return true;
}

bool AvlTree::empty()
{
	return root_ == nullptr;
}

AvlNode *AvlTree::find(AvlNode *t, const int &k)
{
	if (k < t->key)
	{
		t = t->l;
		if (t != nullptr)
			return find(t, k);
	}
	else if (k > t->key)
	{
		t = t->r;
		if (t != nullptr)
			return find(t, k);
	}
	return t;
}

void AvlTree::InOrder()
{
	if (root_ == nullptr)
		return;
	InOrder(root_);
}

void AvlTree::InOrder(AvlNode *t)
{
	if (t != nullptr)
	{
		InOrder(t->l);
		InOrder(t->r);
	}
}

bool AvlTree::remove(AvlNode *t)
{
	if (t->l != nullptr)
		remove(t->l);
	if (t->r != nullptr)
		remove(t->r);

	if (t->p == nullptr)
	{
		delete t;
		t = nullptr;
		return true;
	}

	if (t->p->key > t->key)
		t->p->l = nullptr;
	else
		t->p->r = nullptr;

	delete t;
	t = nullptr;
	return true;
}

void AvlTree::PreOrder()
{
	if (root_ == nullptr)
		return;
	PreOrder(root_);
}

void AvlTree::PreOrder(AvlNode *t)
{
	if (t != nullptr)
	{
		PreOrder(t->l);
		PreOrder(t->r);
	}
}

void AvlTree::BackOrder()
{
	if (root_ == nullptr)
		return;
	BackOrder(root_);
}

void AvlTree::BackOrder(AvlNode *t)
{
	if (t != nullptr)
	{
		BackOrder(t->l);
		BackOrder(t->r);
	}
}

void BTree::BuildTree(const std::vector<int> &val)
{
	for (auto it : val)
	{
		Insert(it);
	}
}

BNode *BTree::CreateNode(int val)
{
	return new BNode(val);
}

bool BTree::Insert(int val)
{
	BNode *node = CreateNode(val);
	if (node == nullptr)
		return false;

	if (m_root == nullptr)
	{
		m_root = node;
		return true;
	}

	BNode *tmp = m_root;
	BNode *last = nullptr;
	while (tmp)
	{
		last = tmp;
		if (val > tmp->val)
		{
			tmp = tmp->r;
		}
		else
		{
			tmp = tmp->l;
		}
	}

	if (val > last->val)
	{
		last->r = node;
	}
	else
	{
		last->l = node;
	}

	return true;
}

void BTree::Clear()
{

}

void BTree::PrintPre()
{
	PrintPre(m_root);
}

void BTree::PrintPre(BNode *n)
{
	if (n)
	{
		PrintPre(n->l);
		PrintPre(n->r);
	}
}